package com.example.algo.addTwoNumbers;

import java.util.Stack;

/**
 * 两数相加
 * 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储一位数字。
 * <p>
 * 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
 * <p>
 * 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
 * <p>
 * 示例：
 * <p>
 * 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
 * 输出：7 -> 0 -> 8
 * 原因：342 + 465 = 807
 */
public class Solution {

    public static void main(String[] args) {
        // 反向链表 342 + 465
        ListNode l1_1 = new ListNode(2);
        ListNode l1_2 = new ListNode(4);
        ListNode l1_3 = new ListNode(3);
        l1_1.next = l1_2;
        l1_2.next = l1_3;
        ListNode l2_1 = new ListNode(5);
        ListNode l2_2 = new ListNode(6);
        ListNode l2_3 = new ListNode(4);
        l2_1.next = l2_2;
        l2_2.next = l2_3;

        ListNode result1 = addTwoNumbers(l1_1, l2_1);
        print(result1);

        // 正向链表 342 + 665
        ListNode l3_1 = new ListNode(3);
        ListNode l3_2 = new ListNode(4);
        ListNode l3_3 = new ListNode(2);
        l3_1.next = l3_2;
        l3_2.next = l3_3;
        ListNode l4_1 = new ListNode(6);
        ListNode l4_2 = new ListNode(6);
        ListNode l4_3 = new ListNode(5);
        l4_1.next = l4_2;
        l4_2.next = l4_3;

//        ListNode result2 = twoNumAdd(l2_1, l3_1);



        // 自己解法
        // 反向链表 342 + 4465
        ListNode l5_1 = new ListNode(2);
        ListNode l5_2 = new ListNode(4);
        ListNode l5_3 = new ListNode(3);
        l5_1.next = l5_2;
        l5_2.next = l5_3;
        ListNode l6_1 = new ListNode(5);
        ListNode l6_2 = new ListNode(6);
        ListNode l6_3 = new ListNode(4);
        ListNode l6_4 = new ListNode(4);
        l6_1.next = l6_2;
        l6_2.next = l6_3;
        l6_3.next = l6_4;

        ListNode head = new ListNode();
        ListNode l1 = l5_1, l2 = l6_1, curr = head;

        int jw = 0;
        while (l1 != null || l2 != null) {
            int a = l1 == null ? 0 : l1.val;
            int b = l2 == null ? 0 : l2.val;
            int value = a + b + jw;
            jw = 0;

            ListNode newNode = new ListNode();
            if (value > 9) {
                jw = value / 10;
                newNode.val = value % 10;
            } else {
                newNode.val = value;
            }
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
            curr.next = newNode;
            curr = curr.next;
        }
        if (jw > 0) {
            curr.next = new ListNode(jw);
        }

        print(head.next);

    }

    public static void print(ListNode node) {
        while (node != null) {
            System.out.print(node.val);
            node = node.next;
        }
        System.out.println();
    }

    /**
     * 反序链表
     * 时间复杂度 O(max(m, n)) 假设 m 和 n 分别表示 l1 和 l2 的长度，次算法最多重复 max(m, n) 次。
     * 空间复杂度 O(max(m, n)) 新列表的长度最多为 max(m, n) + 1
     *
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode p = l1, q = l2, curr = dummyHead;

        int carry = 0;
        while (p != null || q != null) {
            int x = p != null ? p.val : 0;
            int y = q != null ? q.val : 0;
            int z = carry + x + y;
            carry = z / 10;
            curr.next = new ListNode(z % 10);
            curr = curr.next;
            if (p != null) {
                p = p.next;
            }
            if (q != null) {
                q = q.next;
            }
        }
        if (carry > 0) {
            curr.next = new ListNode(carry);
        }

        return dummyHead.next;
    }


    /**
     * 正序链表
     * 先将正向链表圧栈，然后按照反向链表的逻辑操作，将操作结果再压入结果栈，最后将结果栈构造成正向链表
     * 时间复杂度 O(max(m, n)) 假设 m 和 n 分别表示 l1 和 l2 的长度，次算法最多重复 max(m, n) 次。
     * 空间复杂度 O(max(m, n)) 新列表的长度最多为 max(m, n) + 1
     *
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode twoNumAdd(ListNode l1, ListNode l2) {

        /**
         * 链表类的方法简介
         * boolean empty() 判断栈是否为空
         * Object peek() 查看堆栈顶部的对象，但不从堆栈中移除它。
         * Object pop() 移除堆栈顶部的对象，并作为此函数的值返回该对象。
         * Object push() 把数据压入堆栈顶部。
         * int search(Object o) 返回对象在堆栈中的位置，以 1 为基数。
         */
        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();
        while (l1 != null) {
            s1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            s2.push(l2.val);
            l2 = l2.next;
        }

        //进行反序计算
        //结果栈，稍后还需要反置，创建结果链表
        Stack<Integer> rs = new Stack<>();

        int carry = 0;
        while (!s1.empty() || !s2.empty()) {
            int x = s1.peek() != null ? s1.pop() : 0;
            int y = s2.peek() != null ? s2.pop() : 0;
            int z = x + y + carry;
            carry = z / 10;
            rs.push(z % 10);
        }
        if (carry > 0) {
            rs.push(carry);
        }

        //设置一个假的头结点，计算完成后返回它的下一个结点
        ListNode emptyHead = new ListNode(0);
        ListNode curr = emptyHead;
        // 循环结果栈，构造链表
        while (!rs.empty()) {
            curr.next = new ListNode(rs.pop());
            curr = curr.next;
        }
        return emptyHead;
    }
}

